Gerichtete Graphen mit SQL lösen – Teil 1

Eines der bekanntesten und schwierigeren Probleme der Informatik findet sich im Bereich der ‚gerichteten Graphen‘. Ein gerichteter Graph ist eine finite Menge von Knoten, die durch eine Menge von Vektoren (Kanten) verbunden sind. Einen Knoten kann man sich als eine ‚Stadt‘ vorstellen, und jede Kante wäre dann eine ‚Flugverbindung‘ zwischen zwei Städten.

Es gibt eine Vielzahl von Algorithmen und Texten zu diesem Problem, zu Fragen wie: wie viele mögliche Routen gibt es, welche ist die kürzeste, und welche die schnellste Verbindung? Die meisten dieser Algorithmen sind prozedural oder greifen auf Rekursion zurück. Einfacher und hinsichtlich des Programmieraufwandes deutlich ökonomischer wird die Lösung komplexer Probleme mit gerichteten Graphen allerdings mit der deklarativen Sprache SQL.

Im folgenden Beispiel geht es um Flugverbindungen zwischen einzelnen Städten. Hierzu wird eine Tabelle erstellt, die einige imaginäre Daten aufnimmt:

Man kann nicht die CONNECT BY-Syntax verwenden, um herauszufinden, wie man von London nach Sao Paulo gelangt, denn es gibt Daten, die eine Schleife im Graphen erzeugen (Rückflug nach Sao Paulo):

Zur Lösung von Problemen mit gerichteten Graphen muss also eine temporäre Tabelle erstellt werden, die alle möglichen Pfade zwischen zwei Knoten aufnimmt. Dabei muss beachtet werden, dass bereits bearbeitete Pfade nicht dupliziert werden. Außerdem sollen bei diesem Beispiel Pfade unberücksichtigt bleiben, die zum Ausgangsort zurückführen. Zusätzlich kann die Zahl der Zwischenstationen bis zum Ziel aufgezeichnet sowie eine Beschreibung der gewählten Route ausgegeben werden.

Die temporäre Tabelle wird mit Hilfe des folgenden Codes erzeugt: